package com.wxit.algorithm.heap;

import java.util.Arrays;

/**
 * 数据流的中位数
 */
public class LeetCode295 {

    /**
     * 为保证两边数据平衡
     *      两边个数一样时，左边个数加1
     *      两边个数不一样时， 右边个数加1
     *  但是，不能随便加入
     *      左边个数加1时候，把新元素加在右边，弹出右边最小的加入左边
     *      右边个数加1时候，把新元素加在左边，弹出左边最大的加入右边
     * @param num
     */
    public void addNum(int num) {
        if (left.size() == right.size()) {
            right.offer(num);
            left.offer(right.poll());
        } else {
            left.offer(num);
            right.offer(left.poll());
        }
    }

    private Heap left = new Heap(10, true);
    private Heap right = new Heap(10, false);


    /**
     * <li>两边数据一致，左右各取堆顶元素求平均值</li>
     * <li>左边多一个元素，取左边堆顶的元素</li>
     *
     *
     * @return
     */
    public double findMedian() {
        if (left.size() == right.size()) {
            return (left.peek() + right.peek()) / 2.0;
        } else {
            return left.peek();
        }
    }

    @Override
    public String toString() {
        int size = left.size;
        int[] left = new int[size];
        int i = 0;
        for (; i < left.length; i++) {
            left [size - 1 - i] = this.left.array[i];
        }
        int[] right = Arrays.copyOf(this.right.array, this.right.size);
        return Arrays.toString(left) + " <-->" + Arrays.toString(right);
    }

    public static void main(String[] args) {
        LeetCode295 test = new LeetCode295();
        test.addNum(1);
        test.addNum(2);
        test.addNum(3);
        test.addNum(7);
        test.addNum(8);
        test.addNum(9);
        System.out.println(test);
        System.out.println(test.findMedian());
        test.addNum(10);
        System.out.println(test);
        System.out.println(test.findMedian());
        test.addNum(4);
        System.out.println(test);
        System.out.println(test.findMedian());
    }

}
